# @Time    :2025/4/10 10:46
# def quick_sort(alist, first, last):
"""快速排序"""
#     # 从小到大排序
#     if first >= last:
#         return
#
#     mid_value = alist[first]  # 中间值元素 初始化为列表的第一元素
#     low = first  # 初始化两个游标 low在头，hight在尾部
#     hight = last
#     while low < hight:
#         # 1.1，hight 的游标左移 ，遇到比基准值小的时候，hight向左移一步
#         while low < hight and alist[hight] >= mid_value:
#             hight -= 1
#             # 1.2，否则是遇到比基准值小的数字，就把hight所指的元素放到low所指的位置上
#         alist[low] = alist[hight]
#
#         # 2.1，low的游标右 移，判断low+1所指的元素 是否 遇到比基准值大，如果比小 low就一直向右移走，
#         while low < hight and alist[low] < mid_value:
#             low += 1
#             # 2.2否则就把low放到hight的位置
#         alist[hight] = alist[low]
#     # 从循环退出时，low=hight
#     alist[hight] = mid_value
#     # 对low左边的列表执行快速排序
#     quick_sort(alist, first, low - 1)
#     # 对low右边的列表执行快速排序
#     quick_sort(alist, low + 1, last)
#
#
# if __name__ == '__main__':
#     alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
#     print(alist)
#     quick_sort(alist, 0, len(alist) - 1)
#     print(alist)


#--------------------快速排序 另一种方法-------递归调用 然后拼接-----
def quick_sort(alist):
    #如果数组长度
    if len(alist) <= 1:
        return alist
    mid_value = alist[0]
    left = []
    right = []
    for num in alist[1:]:
        while num > mid_value:
            right.append(num)
        else:
            left.append(num)

    return quick_sort(left) + [mid_value] + quick_sort(right)


if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(alist)
    quick_sort(alist, 0, len(alist) - 1)
    print(alist)
